package code.starivan.leetcode;

/**
 * Created by Ivan on 2015/10/23.
 */
/*
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

        Try to solve it in linear time/space.

        Return 0 if the array contains less than 2 elements.

        You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
*/

public class N164_MaximumGap {
    public static void test(){
        int[] nums=new int[]{9,3,1,10};
        System.out.println(new N164_MaximumGap().maximumGap(nums));
    }

    public int maximumGap(int[] nums) {
        if(nums==null||nums.length<=1){
            return 0;
        }

        int max=nums[0];
        int min=nums[0];
        int n=nums.length;
        for(int i=1;i<n;++i){
            max=Math.max(max,nums[i]);
            min=Math.min(min,nums[i]);
        }

        if(max==min){
            return 0;
        }

        boolean[] buckets=new boolean[n+1];
        int[] maxB=new int[n+1];
        int[] minB=new int[n+1];

        for(int i=0;i<n;++i){
            int pos=getPos(max,min,n,nums[i]);
            if(buckets[pos]){
                maxB[pos]=Math.max(maxB[pos],nums[i]);
                minB[pos]=Math.min(minB[pos], nums[i]);
            }else{
                maxB[pos]=nums[i];
                minB[pos]=nums[i];
                buckets[pos]=true;
            }
        }

        int maxDiff=0;
        int lastMax=maxB[0];
        for(int i=1;i<n+1;++i){
            if(buckets[i]){
                maxDiff=Math.max(minB[i]-lastMax,maxDiff);
                lastMax=maxB[i];
            }
        }

        return maxDiff;
    }

    private int getPos(long max,long min,long n,long num){
        return (int)((num-min)*n/(max-min));
    }
}
